package sort;

/**
 * Created with IntelliJ IDEA.
 * Description: 归并排序
 * User: Li_yizYa
 * Date: 2025/9/9
 * Time: 11:45
 */
public class MergeSort {
    private static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }
    private static void merge(int[] nums, int left, int right, int mid) {
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        while (s1 <= e1 && s2 <= e2) { // 两个归并段都有数据
            if (nums[s1] <= nums[s2]) { // <= 确保了它是稳定的排序算法
                tmp[k++] = nums[s1++];
            } else {
                tmp[k++] = nums[s2++];
            }
        }
        while (s1 <= e1) {
            tmp[k++] = nums[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = nums[s2++];
        }
        for (int i = 0; i < k; i++) {
            nums[i + left] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = {6,5,4,4,3,1,2,10,8};
        mergeSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
//    private static void mergeSort(int[] nums, int left, int right) {
//        if (left >= right) {
//            return;
//        }
//        int mid = (left + right) / 2;
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        merge(nums, left, right, mid);
//    }
//    private static void merge(int[] nums, int left, int right, int mid) {
//        int[] tmp = new int[right - left + 1];
//        int k = 0;
//        int s1 = left;
//        int e1 = mid;
//        int s2 = mid + 1;
//        int e2 = right;
//        while (s1 <= e1 && s2 <= e2) {
//            // 两个归并段都有数据
//            if (nums[s1] <= nums[s2]) {
//                tmp[k++] = nums[s1++];
//            } else {
//                tmp[k++] = nums[s2++];
//            }
//        }
//        while (s1 <= e1) {
//            tmp[k++] = nums[s1++];
//        }
//        while (s2 <= e2) {
//            tmp[k++] = nums[s2++];
//        }
//        for (int i = 0; i < k; i++) {
//            nums[i + left] = tmp[i];
//        }
//    }
}
